home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / N_Tree.h < prev    next >
C/C++ Source or Header  |  1992-05-15  |  9KB  |  215 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 07/06/89 -- Initial design
  13. // Updated: MBN 08/15/89 -- Inherit from Generic and initial implementation
  14. // Updated: MBN 09/19/89 -- Added conditional exception handling
  15. // Updated: MBN 02/27/90 -- Added constructor that takes a pointer to node and
  16. //                          the current_depth() member function
  17. // Updated: MJF 03/12/90 -- Added group names to RAISE
  18. // Updated: VDN 02/21/92 -- New lite version
  19. //
  20. // The  N_Tree  class  implements  N-ary  trees,  providing  the organizational
  21. // structure for a tree  (collection) of nodes,  but  knowing nothing about the
  22. // specific type of node  used. N_Tree is parameterized  over a node type and a
  23. // data type, where the node specified  must have a data slot  of the same type
  24. // Type as the N_Tree  class. Two node classes are  provided, but others  could
  25. // also be written.  The  N_Node class implements  static-sized nodes for  some
  26. // particular "N" number of sub-trees, and the D_Node class  implements dymamic
  27. // sized nodes derived from the Vector class.
  28. //
  29. // Since the organization of a tree is important (as  with an expression tree),
  30. // the user must supervise the construction  of  the tree by directing specific
  31. // node and sub-tree assignment and layout.   No attempt  is made by the N_Tree
  32. // class to balance or prune the tree.
  33. //
  34. // The N_Tree class supports the concept  of a  current  position and a current
  35. // traversal mode. When  the traversal  mode  is  set, the current position  is
  36. // invalidated.  The  first call   to advance the   current position causes  an
  37. // internal dynamic cache of pointers to nodes to  be created ordered according
  38. // to the traversal mode. Future current position  methods then act  based upon
  39. // the information in  the cache.   Any method that  changes the tree structure
  40. // invalidates the cache.
  41. //
  42. // There are two  public constructors. The  first takes a  reference  to a Node
  43. // object and constructs an N_Tree object whose root is the supplied node.  The
  44. // second takes a reference  to an existing  N_Tree  object and duplicates  its
  45. // size and contents.  The N_Tree class has four private data slots.  The first
  46. // contains a pointer to the root of the tree, the second maintains the current
  47. // position,  the  third contains a pointer to  a  dynamic cache of pointers to
  48. // nodes used  by  the current  position  methods, and  the   fourth contains a
  49. // pointer to the default node comparison function.  In addition, there are two
  50. // private methods.  The first is used to create the cache of pointers to nodes
  51. // upon the first dispatch to  advance the current position,  and the second is
  52. // the default node comparison function to be used  if the user  does not chose
  53. // to provide one.
  54. //
  55. // All methods  in the  N_Tree class  support  the organization, structure, and
  56. // traversal of a tree.  Methods to allow manipulation  of individual nodes and
  57. // sub-trees is located in the node classes. N_Tree has methods to search for a
  58. // sub-tree,  find a  node with a specific value,  and return a  pointer to the
  59. // parent of the current  node. The reset, next, prev,  value, remove, and find
  60. // methods provide a mechanism to  iterate  through the nodes  of a tree  based
  61. // upon  the current position. The specific  traversal mechanism  for  use with
  62. // this iteration can be set with  the set_traversal method,  and all nodes can
  63. // be removed  from the tree   with  clear.  Finally,  methods  are provided to
  64. // traverse the  tree in  either preorder, inorder,  or  postorder and apply  a
  65. // user-specified function to each node.
  66. //
  67.  
  68. #ifndef N_TREEH                    // If no definition for class
  69. #define N_TREEH
  70.  
  71. #ifndef N_TREE_STATEH
  72. #include <cool/NT_State.h>            // Include NT_State
  73. #endif
  74.  
  75. #ifndef BASE_BINARY_TREEH
  76. enum Left_Right {NONE, LEFT, RIGHT};
  77. enum Traversal_Type {PREORDER, INORDER, POSTORDER,
  78.              PREORDER_REVERSE, INORDER_REVERSE, POSTORDER_REVERSE};
  79. #endif
  80.  
  81. #define CoolN_Tree_state CoolNT_State
  82.  
  83. template <class Node, class Type, int nchild> CoolN_Tree {
  84.   typedef Boolean (*Node##_Apply_Function)(const Type&);    
  85.   DECLARE Node<Type,nchild>;
  86. }
  87.  
  88. template <class Node, class Type, int nchild>
  89. class CoolN_Tree<Node,Type,nchild> {
  90. public:
  91.   CoolN_Tree<Node,Type,nchild> (Node<Type,nchild>* root=NULL); // Default
  92.   CoolN_Tree<Node,Type,nchild> (Node<Type,nchild>& root); // Simple constructor
  93.   CoolN_Tree<Node,Type,nchild> (const CoolN_Tree<Node,Type,nchild>&);    // Copy
  94.   ~CoolN_Tree<Node,Type,nchild> ();        // Destructor
  95.  
  96.   void clear ();                // Empty the tree
  97.   inline long count ();                // Return number of nodes
  98.   inline void reset ();                // Current position invalid
  99.   inline Traversal_Type& traversal ();        // Set/Get the traversal mode
  100.   inline Node##_##Type##_##nchild##_p& operator[] (int); // Set/Get pointers
  101.  
  102.   inline Boolean next ();            // Advance to next node
  103.   Boolean prev ();                    // Backup to previous node
  104.   Type& value ();            // Get value at current position
  105.   Boolean find (const Type&);            // Search for item in tree
  106.   inline CoolNT_State& current_position();        // Get/Set Tree's curpos
  107.   inline long current_depth () const;        // Depth of curpos in tree
  108.  
  109.   void preorder (Node##_Apply_Function);    // Preorder traversal
  110.   void inorder (Node##_Apply_Function);        // Inorder traversal
  111.   void postorder (Node##_Apply_Function);    // Postorder traversal
  112.  
  113.   CoolN_Tree<Node,Type,nchild>& operator= (const CoolN_Tree<Node,Type,nchild>&);
  114.   inline operator Node##_##Type##_##nchild##_p () const; // Conversion to node ptr
  115.  
  116. private:
  117.   Node##_##Type##_##nchild##_p root;        // Root of tree
  118.   long number_nodes;                // Number of nodes in tree
  119.   Traversal_Type t_mode;            // Retains traversal type
  120.   CoolNT_State state;                // Iterator state for CoolN_Tree
  121.  
  122.   void do_count (Node<Type,nchild>*);        // Count nodes in tree
  123.   Boolean next_internal (Traversal_Type);    // Moves current_position
  124.   inline Node<Type,nchild>* copy_nodes(const Node<Type,nchild>*) const; // Copy subnodes
  125.  
  126.   void value_error ();                // Raise exception
  127. };
  128.  
  129. // Reset -- Initialize current position of Tree
  130. // Input:   None
  131. // Output:  None
  132.  
  133. template <class Node, class Type, int nchild> 
  134. inline void CoolN_Tree<Node,Type,nchild>::reset () {
  135.   this->state.stack.clear();
  136. }
  137.  
  138.  
  139. // count -- Return number of nodes in tree
  140. // Input:   None
  141. // Output:  Number of nodes in tree
  142.  
  143. template <class Node, class Type, int nchild> 
  144. inline long CoolN_Tree<Node,Type,nchild>::count () {
  145.   this->number_nodes = 0;            // Initialize count
  146.   this->do_count (this->root);            // Count nodes in tree
  147.   return this->number_nodes;            // Return node count
  148. }
  149.  
  150.  
  151. // set_traversal -- Set traversal mode
  152. // Input:           Traversal type
  153. // Output:          None
  154.  
  155. template <class Node, class Type, int nchild> 
  156. inline Traversal_Type& CoolN_Tree<Node,Type,nchild>::traversal () {
  157.   return (this->t_mode);            // Traversal mode
  158. }
  159.  
  160.  
  161. // operator[] -- Overload the brackets operator to provide a mechanism to set
  162. //               and/or get a sub-tree pointer of a node whose zero-relative
  163. //               index is specified from left to right
  164. // Input:        Zero-relative index into vector of sub-tree pointers
  165. // Output:       Reference to a pointer value
  166.  
  167. template <class Node, class Type, int nchild> 
  168. inline Node##_##Type##_##nchild##_p& CoolN_Tree<Node,Type,nchild>::operator[] (int index) {
  169.   return (this->root->sub_trees[index]);
  170. }
  171.  
  172.  
  173. // next -- Move current position to next node in tree. If no more nodes
  174. //         return FALSE
  175. // Input:  None
  176. // Output: TRUE/FALSE
  177.  
  178. template <class Node, class Type, int nchild> 
  179. inline Boolean CoolN_Tree<Node,Type,nchild>::next () {
  180.   return next_internal (this->t_mode);
  181. }
  182.  
  183.  
  184.  
  185. // current_depth -- Get current depth of current position in tree
  186. // Input:           None
  187. // Output:          Depth of current position node in tree
  188.  
  189. template <class Node, class Type, int nchild>
  190. inline long CoolN_Tree<Node,Type,nchild>::current_depth () const {
  191.   return this->state.stack.length() - 1;
  192. }
  193.  
  194.  
  195. // operator Node -- Provide an accessor to the encapsulated Node object
  196. // Input:           None
  197. // Output:          Pointer to node object
  198.  
  199. template <class Node, class Type, int nchild> 
  200. inline CoolN_Tree<Node,Type,nchild>::operator Node##_##Type##_##nchild##_p () const
  201. {
  202.   return this->root;
  203. }
  204.  
  205.  
  206. template <class Node, class Type, int nchild>
  207. inline Node<Type,nchild>* CoolN_Tree<Node,Type,nchild>::copy_nodes(const Node<Type,nchild>* n) const{
  208.   Node<Type,nchild>* new_nodes = NULL;
  209.   if (n)
  210.     new_nodes = n->copy_nodes(n);        // recursive deep copy
  211.   return new_nodes;
  212. }
  213.  
  214. #endif                        // End N_TREEH #if
  215.